package com.demo.leetcode;

/**
 * 删除链表的倒数第N个节点
 */
public class leetcode19 {
    /**
     * 给定一个链表，删除链表的倒数第 _n_ 个节点，并且返回链表的头结点。

     示例：
     给定一个链表: 1->2->3->4->5, 和 _n_ = 2.
     当删除了倒数第二个节点后，链表变为 1->2->3->5.
     说明：
     给定的 _n_ 保证是有效的。
     进阶：
     你能尝试使用一趟扫描实现吗？
     */

    /**
     * 思路：
     * 1、遍历链表节点获取链表的最大长度
     * 2、如果删除的倒数第N个节点有效，直接将删除节点的前一节点指向后面的节点
     */
    public static Node removeNthFromEnd(Node head, int n) {
        Node tmp = head;
        int len = 0;
        while (tmp != null) {
            tmp = tmp.next;
            len++;
        }
        if (n == len) {
            return head.next;
        }
        tmp = head;
        int cut = len - n;//要删除的节点的前一个节点
        while (cut-- > 1) {
            tmp = tmp.next;
        }
        if (tmp.next != null) {
            tmp.next = tmp.next.next;
            return head;
        }
        return null;
    }

    public static void main(String[] args) {
        Node a = new Node("1");
        Node b = new Node("2");
        Node c = new Node("3");
        Node d = new Node("4");
        Node e = new Node("5");
        a.next=b;
        b.next=c;
        c.next=d;
        d.next=e;
        Node node = removeNthFromEnd(a, 2);
        System.out.println(node.obj);
    }


    static class Node {
        Object obj;
        Node next;

        public Node(Object obj) {
            this.obj = obj;
        }
    }
}

